#include <iostream>
using namespace std;
 
const int N = 10007;
int f[N];
 
void setFib()
{
    f[1] = 1, f[2] = 2;
    for(int i = 3; i < N; ++i)
    {
        f[i] = f[i - 1] + f[i - 2];
        f[i] %= 10000;
    }
}
 
int main()
{
    setFib();
    int n = 0;
    while(cin >> n)
    {
        for(int i = 0; i < n; ++i)
        {
            int x = 0;
            cin >> x;
            printf("%04d", f[x] % 10000);
        }
        cout << endl;
    }
    return 0;
}